`
https://leetcode.cn/problems/permutations-ii/
`

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const res = []

  const track = []

  const used = new Array(nums.length).fill(false)
  // 数组有重复元素，预先排序，方便剪枝
  nums.sort((a, b) => a - b)

  const backtrack = () => {
    if (track.length === nums.length) {
      res.push([...track])
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) {
        continue
      }

      // 重复结果出现的原因是出现了相同的元素以不同的顺序进行排列
      // 例如 [1, 2, 2'] 和 [1, 2', 2]，其中 2 和 2' 是相同的元素
      // 类似于排序中的不稳定排序结果，我们只需要保证相同元素的相对顺序不变即可
      // 标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列
      // 但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
        continue
      }

      track.push(nums[i])
      used[i] = true
      backtrack()
      used[i] = false
      track.pop()
    }
  }

  backtrack()
  return res
};